package Algorithm.dfs;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * 迷宫问题
 * 给定一个包含0和1的矩阵，1为通道，0为墙壁，求从第一列任意一个入口到达最后一列任意一个出口中的最短路径
 */
public class MazeProblem {

    /**
     * 思路一：BFS。抽象为一个图或者说森林结构，第一列所有的1为根节点，子节点即为邻接节点，因此通过广度优先遍历即可确定每一个节点距离根节点的最短路径
     * 每一层入队的节点都是和根节点最短路径长度相同的节点
     */
    public int bfs(int[][] maze) {
        int m = maze.length, n = maze[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[m][n];
        for (int i = 0;i < m;i++) {
            if (maze[i][0] == 1) {
                queue.add(new int[]{i, 0, 1});
                visited[i][0] = true;
            }
        }
        int shortest = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1], dist = cur[2];
            if (y == n- 1) shortest = Math.min(shortest, dist);
            int[] dx = {-1, 1,0, 0};
            int[] dy = {0, 0,-1, 1};

        }
    }

    /**
     * 思路二：DFS回溯。抽象为一个图或者说森林结构，第一列所有的1为根节点，子节点即为邻接节点.
     * dfs过程中使用一个visited数组保存已访问节点，回溯时重置
     */
    public int dfs(int[][] maze) {
}
